package com.chj.kmp;

public class Code_04_01_Manacher {

	public static char[] manacherString(String str) {
		char[] charArr = str.toCharArray();
		char[] res = new char[str.length() * 2 + 1];
		int index = 0;
		for (int i = 0; i != res.length; i++) {
			res[i] = (i & 1) == 0 ? '#' : charArr[index++];
		}
		return res;
	}

	public static int maxLcpsLength(String str) {
		if (str == null || str.length() == 0) {
			return 0;
		}
		char[] charArr = manacherString(str);
		int[] pArr = new int[charArr.length];
		int index = -1;
		int pR = -1;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i != charArr.length; i++) {
//			pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
//			while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
//				if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
//					pArr[i]++;
//				else {
//					break;
//				}
//			}
//			if (i + pArr[i] > pR) {
//				pR = i + pArr[i];
//				index = i;
//			}

			System.out.println("===pArr====");
			// i在R外
			if (i >= pR) {
				while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
					if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
						pArr[i]++;
					else {
						break;
					}
				}

				if (i + pArr[i] > pR) {
					pR = i + pArr[i];
					index = i;
				}
			}

			// i在R内
			if (i < pR) {

				// i的对应点i* 回文半径在L外
				if (pR - i < pArr[2 * index - i]) {
					pArr[i] = pR - i;

					// i的对应点i* 回文半径在L上
				} else if (pR - i == pArr[2 * index - i]) {
					while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
						if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
							pArr[i]++;
						else {
							break;
						}
					}

					if (i + pArr[i] > pR) {
						pR = i + pArr[i];
						index = i;
					}

					// i的对应点i* 回文半径在L内
				} else {
					pArr[i] = pArr[2 * index - i];
				}
			}
			System.out.println(String.valueOf(charArr[i]));
			System.out.println(pArr[i]);
			System.out.println("===pArr====");
			max = Math.max(max, pArr[i]);
		}
		return max - 1;
	}

//	https://blog.csdn.net/m0_38109046/article/details/88029844
//	https://blog.csdn.net/u013453787/article/details/82973397
	public static void main(String[] args) {
		String str1 = "abc1234321ab";
		System.out.println(maxLcpsLength(str1));
	}

}
